package parser.table;

import static common.Constants.EMPTY;
import static common.Constants.MARKER;
import java.util.LinkedList;
import java.util.List;
import structures.grammar.Grammar;
import structures.grammar.ItemList;
import structures.grammar.Rule;
import structures.table.LRTable;
import structures.table.Situation;
import structures.table.SituationSet;
import structures.table.action.Accept;
import structures.table.action.Reduce;
import structures.table.action.Shift;
import structures.table.action.Transition;
import structures.table.symboltable.ItemInfo;
import structures.table.symboltable.TerminalItemInfo;

/**
 *
 * @author Slayer
 */
public class TableBuilder {

    private Grammar extendedGrammar;
    private ItemList listWithEMPTY;
    private LRTable actions;
    private LRTable gotos;

    public TableBuilder(Grammar grammar) {
        this.extendedGrammar = grammar;
        extendedGrammar.extend();
        listWithEMPTY = new ItemList();
        listWithEMPTY.add(EMPTY);
    }

    private ItemList addUniqueSymbols(ItemList base, ItemList newChars) {
        for (ItemInfo item : newChars) {
            if (!base.contains(item)) {
                base.add(item);
            }
        }

        return base;
    }

    /**
     * Gets set FIRST of specified symbol.
     *
     * @param symbol Symbol
     * @return List of terminals, i.e. FIRST set.
     */
    private ItemList getFIRSTSet(ItemInfo symbol) {
        ItemList set = new ItemList();
        ItemList buf;
        boolean allSetsContainEmpty = true;


        //Step 1
        if (symbol instanceof TerminalItemInfo) { // symbol is terminal
            set.add(symbol);
            return set;
        } else { // symbol is not terminal
            //Step 2

            /*
             * Check, if there is rule symbol->empty
             */
            for (Rule rule : extendedGrammar.get(symbol.getName())) {
                if (rule.getTo().isEmptyExpansion()) {
                    set.add(EMPTY);
                    break;
                }
            }

            //Step 3
            //1)
            for (Rule rule : extendedGrammar.get(symbol.getName())) {
                ItemList exp = rule.getTo();
                if (!exp.isEmptyExpansion()) {
                    for (ItemInfo symb : exp) {
                        buf = getFIRSTSet(symb);
                        set = addUniqueSymbols(set, buf);
                        if (buf.indexOf(EMPTY) == -1) {
                            allSetsContainEmpty = false;
                            break;
                        }
                    }
                    //2)
                    if (allSetsContainEmpty) {
                        set = addUniqueSymbols(set, listWithEMPTY);
                    }
                }
            }
        }

        return set;
    }

    /**
     * Gets set FIRST for specified set of symbols
     *
     * @param exp
     * @return
     */
    private ItemList getFIRSTExpansionSet(ItemList exp) {
        ItemList set = new ItemList();
        ItemList buf;
        boolean allSetsContainEmpty = true;
        boolean containsEmpty;

        for (ItemInfo symbol : exp) {
            buf = getFIRSTSet(symbol);
            containsEmpty = buf.remove(EMPTY);
            set = addUniqueSymbols(set, buf);
            if (!containsEmpty) {
                allSetsContainEmpty = false;
                break;
            }
        }

        if (allSetsContainEmpty) {
            set = addUniqueSymbols(set, listWithEMPTY);
        }

        return set;
    }

    private SituationSet closure(SituationSet situationsSet) {
        SituationSet result = (SituationSet) situationsSet.clone();
        SituationSet buffer;
        boolean canBeAdded;
        int startIndex = 0;

        do {
            buffer = new SituationSet();//clear buffer
            canBeAdded = false;

            for (int index = startIndex; index < result.size(); ++index) {
                Situation situation = result.get(index);        //get current situation
                //ItemList alpha = situation.getAlpha();          //alpha of situation
                ItemList beta = situation.getBeta();            //beta of situation
                ItemInfo B = situation.getB();                      //B of situation
                List<Rule> rules = extendedGrammar.get(B.getName());

                if (rules == null) {
                    continue;
                }

                ItemList betaAndAvanchain = (ItemList) beta.clone();
                betaAndAvanchain.add(situation.getAvanChain());
                ItemList FIRST = getFIRSTExpansionSet(betaAndAvanchain); //get FIRST set of beta + a

                for (Rule rule : rules) {
                    for (ItemInfo terminal : FIRST) {
                        Situation closure = new Situation(rule, terminal);

                        if (!buffer.contains(closure) && !result.contains(closure)) {
                            buffer.add(closure);
                            canBeAdded = true;
                        }
                    }
                }
            }

            startIndex = result.size();
            result.addAll(buffer);
        } while (canBeAdded);

        return result;
    }

    private SituationSet gotoX(SituationSet situationsSet, ItemInfo X) {
        SituationSet result = new SituationSet();


        for (Situation situation : (SituationSet) situationsSet.clone()) {
            ItemInfo B = situation.getB();              //B of situation

            if (B.equals(X)) {
                if (situation.movePoint()) {
                    result.add(situation);
                }
            }
        }

        return closure(result);
    }

    protected List<SituationSet> items() {
        List<SituationSet> canonicalSystem = new LinkedList<SituationSet>();
        List<SituationSet> buffer;
        boolean canBeAdded;
        int startIndex = 0;

        canonicalSystem.add(closure(new SituationSet(new Situation(extendedGrammar.getFirstRule(), MARKER))));

        do {
            canBeAdded = false;
            buffer = new LinkedList<SituationSet>();

            for (int index = startIndex; index < canonicalSystem.size(); ++index) {
                SituationSet situationSet = canonicalSystem.get(index);

                for (ItemInfo X : extendedGrammar.getUniqueItems()) {
                    SituationSet set = gotoX(situationSet, X);

                    if (!set.isEmpty() && !canonicalSystem.contains(set) && !buffer.contains(set)) {
                        buffer.add(set);
                        canBeAdded = true;
                    }
                }
            }

            startIndex = canonicalSystem.size();
            canonicalSystem.addAll(buffer);
        } while (canBeAdded);

        return canonicalSystem;
    }
    
    protected int getStateNumber(List<SituationSet> list, SituationSet set) {
        return list.indexOf(set);
    }

    public void build() {
        List<SituationSet> canonicalSystem = items();
        int stateNum = canonicalSystem.size();

        //init tables
        actions = new LRTable(stateNum);
        gotos = new LRTable(stateNum);

        for (int stateI = 0; stateI < stateNum; ++stateI) {
            SituationSet set = canonicalSystem.get(stateI);

            for (Situation situation : set) {
                //ItemList alpha = situation.getAlpha();
                ItemInfo B = situation.getB();


                if (!B.equals(EMPTY)) {
                    //shift j
                    SituationSet setJ = gotoX(set, B);
                    int j = getStateNumber(canonicalSystem, setJ);

                    if (B instanceof TerminalItemInfo) {
                        actions.put(stateI, B, new Shift(j));
                    } else {
                        gotos.put(stateI, B, new Transition(j));
                    }
                } else if (!situation.getRule().getFrom().equals(extendedGrammar.getFirstSymbol())) {
                    //reduce A -> alpha
                    actions.put(stateI, situation.getAvanChain(), new Reduce(situation.getRule()));
                } else if (situation.getAvanChain().equals(MARKER)) {
                    //accept
                    actions.put(stateI, MARKER, new Accept());
                }
            }
        }
    }

    public LRTable getActions() {
        return actions;
    }

    public LRTable getGotos() {
        return gotos;
    }
}
